﻿#include <iostream>
#include <queue>
#include "Graph.h"

static struct EdgeComparator
{
	bool operator()(const GraphEdge* a, const GraphEdge* b)
	{
		return a->weight > b->weight;
	}
};

static void kruskal(const Graph* graph, unordered_set<GraphEdge*>& edgeSet)
{
	unordered_map<GraphNode*, unordered_set<GraphNode*>*> dic;
	priority_queue<GraphEdge*, vector<GraphEdge*>, EdgeComparator> heap;
	// 防止重复析构 unordered_set<GraphNode*>*
	unordered_set<unordered_set<GraphNode*>*> willDeletedSet;

	for (auto nodePairIterator = graph->nodes.begin(); nodePairIterator != graph->nodes.end(); ++nodePairIterator)
	{
		unordered_set <GraphNode*>* nodeSet = new unordered_set<GraphNode *>();
		GraphNode* node = nodePairIterator->second;
		nodeSet->insert(node);
		dic.insert({ node, nodeSet, });
	}

	for (auto edgeIterator = graph->edges.begin(); edgeIterator != graph->edges.end(); ++edgeIterator)
	{
		heap.push(*edgeIterator);
	}

	while (!heap.empty())
	{
		auto topEdge = heap.top();
		heap.pop();
		auto fromPair = dic.find(topEdge->from);
		auto toPair = dic.find(topEdge->to);

		if (fromPair->second == toPair->second)
		{

		}
		else
		{
			if (willDeletedSet.find(fromPair->second) != willDeletedSet.end())
				continue;

			if (willDeletedSet.find(toPair->second) != willDeletedSet.end())
				continue;

			edgeSet.insert(topEdge);
			for (auto nodeIterator = toPair->second->begin(); nodeIterator != toPair->second->end(); ++nodeIterator)
			{
				fromPair->second->insert(*nodeIterator);
			}

			auto toSet = toPair->second;
			willDeletedSet.insert(toSet);
			dic[topEdge->to] = fromPair->second;

			if (fromPair->second->size() == graph->nodes.size()) 
				break;
		}
	}

	for (auto delPair = dic.begin(); delPair != dic.end(); ++delPair)
	{
		if (willDeletedSet.find(delPair->second) != willDeletedSet.end())
			continue;

		willDeletedSet.insert(delPair->second);
	}

	for (auto delIterator = willDeletedSet.begin(); delIterator != willDeletedSet.end(); ++delIterator)
	{
		delete(*delIterator);
	}
}

/**
 * 最小生成树，Kruskal算法
 * 要求：无向图
 *
 *              A----5-----B----------1000--------E
 *              | \        |
 *              |   \      |
 *              3     30   2
 *              |       \  |
 *              |         \|
 *              C---15-----D
 *
 * A,B,C,D,E每个点分别做成1个独立的集合，每个集合只包括自己，也就是1个点
 * 将所有的边按照weight从小到大排序，然后依次看每条边的2个点, 是否属于同一个集合。
 * 如果不属于同一个集合，则将这两个点合入同一个集合内，然后处理下一条边；
 * 如果属于同一个集合，直接处理下一条边。
 *
 * 如上述例子，所有边按照weight排序: B-D, A-C, A-B, C-D, A-D, B-E
 * 集合: {A}, {B}, {C}, {D}, {E}
 * 1. B-D: {A}, {B, D}, {C}, {E}, 取这条边
 * 2. A-C: {A, C}, {B, D}, {E}, 取这条边
 * 3. A-B: {A, B, C, D}, {E}, 取这条边
 * 4. C-D: 集合不变, 不取这条边
 * 5. A-D: 集合不变, 不取这条边
 * 6. B-E: {A, B, C, D, E}, 取这条边
 * 故 最小生成树，由B-D, A-C, A-B, B-E组成。
 */
int main_Kruskal()
{
	int matrix[][3] = {
		{'a', 'b', 6},
		{'a', 'c', 1},
		{'a', 'd', 5},
		{'b', 'c', 5},
		{'b', 'e', 3},
		{'c', 'd', 5},
		{'c', 'e', 6},
		{'c', 'f', 4},
		{'d', 'f', 2},
		{'e', 'f', 6},
	};

	int* pMatrix = matrix[0];
	Graph* graph = Graph::generate(&pMatrix, sizeof(matrix) / sizeof(int) / 3, 3, false);
	unordered_set<GraphEdge*> edgeResults;
	kruskal(graph, edgeResults);

	for (auto edgeIterator = edgeResults.begin(); edgeIterator != edgeResults.end(); ++edgeIterator)
	{
		auto edge = *edgeIterator;
		printf("%c->%c %d\n", edge->from->value, edge->to->value, edge->weight);
	}

	delete(graph);
	return 0;
}